﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<algorithm>
using namespace std;
int wiggleMaxLength(vector<int>& nums) {
	int n = nums.size();
	vector<int> f(n, 1), g(n, 1);
	int ret = 1;
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (nums[i] > nums[j])
				f[i] = max(f[i], g[j] + 1);
			else if (nums[i] < nums[j])
				g[i] = max(g[i], f[j] + 1);
		}
		ret = max(ret, max(f[i], g[i]));
	}
	return ret;
}
int findNumberOfLIS(vector<int>& nums) {
	int n = nums.size();
	vector<int> len(n, 1), count(n, 1);
	int lenmax = 1, ret = 1;
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (nums[j] < nums[i])
			{
				if (len[i] < len[j] + 1)// 重新计数
				{
					len[i] = len[j] + 1;
					count[i] = count[j];
				}
				else if (len[i] == len[j] + 1)
				{
					count[i] += count[j];
				}
			}
		}
		if (lenmax < len[i])// 重新计数
		{
			lenmax = len[i];
			ret = count[i];
		}
		else if (lenmax == len[i])
			ret+=count[i];
	}
	return ret;
}
int findLongestChain(vector<vector<int>>& pairs) {
	sort(pairs.begin(), pairs.end());
	int n = pairs.size();
	vector<int> dp(n,1);
	int ret = 1;
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (pairs[j][1] < pairs[i][0])
				dp[i] = max(dp[i], dp[j] + 1);
		}
		ret = max(ret, dp[i]);
	}
	return ret;
}
int longestSubsequence(vector<int>& arr, int difference) {
	int n = arr.size();
	unordered_map<int, int> hash;// {arr[i], dp[i]}
	hash[arr[0]] = 1;
	int ret = 1;
	for (int i = 1; i < n; i++)
	{
		int a = arr[i] - difference;
		hash[arr[i]] = hash[a] + 1;
		ret = max(ret, hash[arr[i]]);
	}
	return ret;
}
int lenLongestFibSubseq(vector<int>& arr) {
	int n = arr.size();
	unordered_map<int, int> hash;//记录某个数在数组中的下标
		hash[arr[0]] = 0;
	vector<vector<int>> dp(n, vector<int>(n, 2));
	int ret = 0;
	for (int i = 1; i < n; i++)// 固定倒数第⼆个位置
	{
		for (int j = i + 1; j < n; j++)// 固定最后⼀个位置
		{
			int a = arr[j] - arr[i];
			if(hash.count(a))
			dp[i][j] = dp[hash[a]][j] + 1;
			ret = max(ret, dp[i][j]);// 统计表中的最⼤值
		}
		hash[arr[i]] = i;//保证a的下标小于i
	}
	return ret;
}
int longestArithSeqLength(vector<int>& nums) {
	int n = nums.size();
	vector<vector<int>> dp(n, vector<int>(n, 2));
	unordered_map<int, int> hash;
	int ret = 2;
	for (int i = 1; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			int a = 2 * nums[i] - nums[j];
			if (hash.count(a))
				dp[i][j] = dp[hash[a]][i] + 1;
			ret = max(ret, dp[i][j]);
		}
		hash[nums[i]] = i;
	}
	return ret;
}
int numberOfArithmeticSlices(vector<int>& nums) {
	int n = nums.size();
	vector<vector<int>> dp(n, vector<int>(n, 0));
	unordered_map<int, vector<int>> hash;
	hash[nums[0]].push_back(0);
	int ret = 0;
	for (int i = 1; i < n; i++)
	{
		for (int j = 2; j < n; j++)
		{
			int a = 2 * nums[i] - nums[j];
			if (hash.count(a))
			{
				for (int k = 0; k < hash[a].size(); k++)
					dp[i][j] += dp[hash[a][k]][i] + 1;
			}
			ret += dp[i][j];
		}
		hash[nums[i]].push_back(i);
	}
	return ret;
}
int main()
{
	return 0;
}